#include <bits/stdc++.h>

using namespace std;

// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void f(TreeNode* root, int sum, int target)
    {
        // 叶子节点
        if(root->left == nullptr && root->right == nullptr)
        {
            if(root->val + sum == target)
            {
                path.push_back(root->val);
                ret.emplace_back(path);
                path.pop_back();
            }
        }
        else // 不是叶子节点
        {
            path.push_back(root->val);
            if(root->left) f(root->left, sum + root->val, target);
            if(root->right) f(root->right, sum + root->val, target);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int target) 
    {
        if(root) f(root, 0, target);
        return ret; 
    }
};


class Solution 
{
private:
    vector<vector<int>> ret;
    vector<int> path;

    void dfs(TreeNode* root, int targetSum)
    {
        if(root == nullptr)
            return;
        
        path.emplace_back(root->val);
        targetSum -= root->val;
        // 收集结果
        if(root->left == nullptr && root->right == nullptr && targetSum == 0)
            ret.emplace_back(path);
        
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);

        path.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
        dfs(root, targetSum);
        return ret;
    }
};